package leetcode.editor.cn.dsa09_doublequeue;
//给定一个字符串，逐个翻转字符串中的每个单词。

public class ReverseWordsInAString151_3 {
    public static void main(String[] args) {
        ReverseWordsInAString151_3.Solution solution = new ReverseWordsInAString151_3().new Solution();
        System.out.println(solution.reverseWords("the sky is blue"));
        System.out.println(solution.reverseWords("  hello world!  "));
        System.out.println(solution.reverseWords("a good   example"));
        System.out.println(solution.reverseWords("  Bob    Loves  Alice   "));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 解法四：先翻转整个字符串，在翻转每个单词，注意多余空格的处理
         * @param s
         * @return
         */
        public String reverseWords(String s) {
            char[] array = s.toCharArray();
            // 1.先翻转整个字符串
            swap(array, 0 , array.length - 1);
            int start = -1, // 定位每个单词开始索引
                end = 0; // 定位最后一个单词的结束空格，需要去除掉
            for (int i = 0; i < array.length; i++) {
                char c = array[i];
                if (c != ' ') {
                     if(start == -1) start = i;
                } else {
                    if(start != -1) {
                        // 2.翻转每一个单词
                        swap(array, start, i - 1);
                        start = -1; // 重置开始索引
                        end = i; // 记录结束空格的索引
                    } else {
                        array[i] = '@'; // 需要去除的多余空格，使用非法字符做个标记
                    }
                }
            }
            if(start != -1) { // 最后一个字符是非空格，需要再次翻转
                swap(array, start, array.length - 1);
            } else { // 字符结尾有空格，标记最后一个单词的相邻空格
                array[end] = '@';
            }
            StringBuilder sb = new StringBuilder();
            for (char c : array) {
                if (c != '@') { // 跳过多余空格
                    sb.append(c);
                }
            }
            return sb.toString();
            //return new String(array).replace("@", "");
        }
        // 翻转数组指定索引的字符
        private void swap (char[] chars, int start, int end) {
            while (start < end) {
                char c = chars[start];
                chars[start++] = chars[end];
                chars[end--] = c;
            }
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}
